package leetcode_800;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *PartitionLabels_763 给定一个字符串 里面保存着字符 求最多的区间 每一个区间都不含有其他区间的字符 
 *describe:遍历 不停改变遍历窗口大小 用map记录边界 AC 33%
 *2018年10月18日 下午2:28:20
 */
public class PartitionLabels_763 {
	public static void main(String[] args) {
		PartitionLabels_763 test=new PartitionLabels_763();
		test.partitionLabels("ababcbacadefegdehijhklij");
	}
	
	public List<Integer> partitionLabels(String S) {
        Map<Character,int []> map=new HashMap<Character,int[]>();//其实第一个位置不需要知道 所以可以优化 用数组记录最后一个位置
        char []chars=S.toCharArray();
        for(int i=0;i<chars.length;++i) {//建立最长区间映射
        	char now=chars[i];
        	int[] index=map.get(now);
        	if(index==null) {
        		index=new int[] {i,i};
        	}
        	else {
        		index[1]=i;
        	}
        	map.put(now, index);
        }
        List<Integer> res=new ArrayList<Integer>();
        int end=map.get(chars[0])[1],start=0;
        while(end!=chars.length-1) {//最后一个区间并不是最右
        	int before=start;//标记前一位
        	while(start<end) {
        		int temp=map.get(chars[++start])[1];
        		if(temp>end) {
        			end=temp;
        			continue;//重新开始遍历 确定区间
        		}
        	}
        	//结束的时候 便是一个区间被划分的时候
        	start++;
        	if(start==S.length()) {
        		 res.add(S.length()-before);//是所有区间被走完
        		 return res;
        	}
        	end=map.get(chars[start])[1];
        	res.add(start-before);
        }
        res.add(S.length()-start);//是最后一个区间没走
        return res;
    }
}
